#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const double pi = acos(-1.0);  // 高精度圆周率
const double eps = 1e-8;       // 偏差值
const int maxp = 1010;         // 点的数量
// 判断是否等于零，返回0为等于零，返回-1为小于，1为大于
int sgn(double x) {
  if (fabs(x) < eps)
    return 0;
  else
    return x < 0 ? -1 : 1;
}

// 判断是否相等，返回0为相等，返回-1为小于，1为大于
int dcmp(double x, double y) {
  if (fabs(x - y) < eps)
    return 0;
  else
    return x < y ? -1 : 1;
}

// 三维几何
struct Point3 {
  double x, y, z;
  Point3() {}
  Point3(double x, double y, double z) : x(x), y(y), z(z) {}
  Point3 operator+(Point3 B) { return Point3(x + B.x, y + B.y, z + B.z); }
  Point3 operator-(Point3 B) { return Point3(x - B.x, y - B.y, z + B.z); }
  Point3 operator*(double k) { return Point3(x * k, y * k, z * k); }  // 放大k倍
  Point3 operator/(double k) { return Point3(x / k, y / k, z / k); }  // 缩小k倍
  bool operator==(Point3 B) {
    return sgn(x - B.x) == 0 && sgn(y - B.y) == 0 && sgn(z - B.z) == 0;
  }
};

typedef Point3 Vector3;
// 两点距离
double Distance(Point3 A, Point3 B) {
  return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y) +
              (A.z - B.z) * (A.z - B.z));
}

struct Line3 {
  Point3 p1, p2;
  Line3() {}
  // 根据端点确定直线
  Line3(Point3 p1, Point3 p2) : p1(p1), p2(p2) {}
};

typedef Line3 Segment3;
// 向量点积
double Dot(Vector3 A, Vector3 B) { return A.x * B.x + A.y * B.y + A.z * B.z; }

// 向量长度
double vector_length(Vector3 A) { return sqrt(Dot(A, A)); }

// 向量长度平方
double vector_length_square(Vector3 A) { return Dot(A, A); }

// 向量夹角
double Angle(Vector3 A, Vector3 B) {
  return acos(Dot(A, B) / vector_length(A) / vector_length(B));
}

// 向量叉积；大于0，B在A逆时针方向；等于0，A、B重合
Vector3 Cross(Vector3 A, Vector3 B) {
  return Point3(A.y * B.z - A.z * B.y, A.z * B.x - A.x * B.z,
                A.x * B.y - A.y * B.x);
}

// 三点构成平行四边形面积(A为公共点)
double Area2(Point3 A, Point3 B, Point3 C) {
  return vector_length(Cross(B - A, C - A));
}

// 判断p是否在三角形ABC内,可以用Area2来计算;如果点p在三角形内部,那么用点p对三角形ABC进行刨分,形成的3个三角形的面积应和直接计算ABC的面积相等

// dcmp(Area2(p, A, B) + Area2(p, B, C) + Area2(p, C, A), Area2(A, B, C)) == 0;

// 点在直线上
bool Point_line_relation(Point3 p, Segment3 v) {
  return sgn(vector_length(Cross(v.p1 - p, v.p2 - p))) == 0 &&
         sgn(Dot(v.p1 - p, v.p2 - p)) == 0;
}

// 点到直线的距离
double Dis_point_line(Point3 p, Line3 v) {
  return vector_length(Cross(v.p2 - v.p1, p - v.p1) / Distance(v.p1, v.p2));
}

// 点在直线上的投影
Point3 Point_line_proj(Point3 p, Line3 v) {
  double k = Dot(v.p2 - v.p1, p - v.p1) / vector_length_square(v.p2 - v.p1);
  return v.p1 + (v.p2 - v.p1) * k;
}

// 点到线段的距离
double Dis_point_seg(Point3 p, Segment3 v) {
  if (sgn(Dot(p - v.p1, v.p2 - v.p1)) < 0 ||
      sgn(Dot(p - v.p2, v.p1 - v.p2)) < 0)  // 点的投影不在线段上
    return min(Distance(p, v.p1), Distance(p, v.p2));
  return Dis_point_line(p, v);  // 点的投影在线段上
}

// 三维 : 平面
struct Plane {
  Point3 p1, p2, p3;
  Plane() {}
  Plane(Point3 p1, Point3 p2, Point3 p3) : p1(p1), p2(p2), p3(p3) {}
};

// 平面法向量
Point3 pvec(Point3 A, Point3 B, Point3 C) { return Cross(B - A, C - A); }
Point3 pvec(Plane f) { return Cross(f.p2 - f.p1, f.p3 - f.p1); }

// 四点共平面
bool Point_on_plane(Point3 A, Point3 B, Point3 C, Point3 D) {
  return sgn(Dot(pvec(A, B, C), D - A)) == 0;
}

// 两平面平行
int parallel(Plane f1, Plane f2) {
  return vector_length(Cross(pvec(f1), pvec(f2))) < eps;
}

// 两平面垂直
int vertical(Plane f1, Plane f2) { return sgn(Dot(pvec(f1), pvec(f2))) == 0; }

// 直线与平面的交点p,返回值是交点的个数
int Line_cross_plane(Line3 u, Plane f, Point3 &p) {
  Point3 v = pvec(f);  // 平面的法向量
  double x = Dot(v, u.p2 - f.p1);
  double y = Dot(v, u.p1 - f.p1);
  double d = x - y;
  if (sgn(x) == 0 && sgn(y) == 0) return -1;  // v在f上
  if (sgn(d) == 0) return 0;                  // v与f平行
  p = ((u.p1 * x) - (u.p2 * y)) / d;          // v与f相交
  return 1;
}

// 四面体有向体积X6
double volume4(Point3 A, Point3 B, Point3 C, Point3 D) {
  return Dot(Cross(B - A, C - A), D - A);
}
